home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / MPW_C / SPELL__ / CHECK.C next >
Text File  |  1990-07-03  |  3KB  |  109 lines
  1. /*
  2.  
  3.     File:    check.c
  4.     Author:  Graham Toal
  5.     Purpose: Check a word using DAWG or TRIE.
  6.     Functions exported:  dawg_check, pack_check
  7.     Internal function:   dawg_ck, pack_ck
  8.  
  9. Description:
  10.  
  11.     call as:     dawg_check(dawg, "word")
  12.                  pack_check(trie, "word")
  13.  
  14.    Simple spelling-check. Unfortunately the two interfaces for
  15.    DAWGs and TRIEs are different, and even DAWG stuff differs from
  16.    program to program.  The problem is primarily in how to spot
  17.    the end of a search; at the moment it is done when a particular
  18.    pointer points to the root. Unfortunately we enter the data
  19.    structure either at root+1 or at some arbitrary point, so this
  20.    scheme means passing in two pointers.  The next idea is to check
  21.    that the *data* pointed to by the terminating pointer is 0; this
  22.    would be OK but I was hoping to leave the initial word in the
  23.    dawg free for expansion... (dawg contains [0, Node1..NodeN])
  24.  
  25.    *best* idea would be to terminate on *INDEX* being 0.  This is
  26.    probably also simplest & I'll code it up properly when I'm awake...
  27.  
  28. */
  29.  
  30. static int
  31. #ifdef PROTOTYPES
  32. dawg_ck(NODE PCCRAP *dict, NODE PCCRAP *edge, char *word)
  33. #else
  34. dawg_ck(dict, edge, word)
  35. NODE PCCRAP *dict;
  36. NODE PCCRAP *edge;
  37. char *word;
  38. #endif
  39. {
  40.   if (edge == dict) return(0!=0);
  41.   for (;;) {
  42.     if (*word == (((*edge >> V_LETTER) & M_LETTER))) {
  43.       if (*++word == '\0') {
  44.         return((*edge & M_END_OF_WORD) != 0);
  45.       } else {
  46.         if ((edge = dict+(*edge & M_NODE_POINTER)) == dict) break;
  47.         continue;
  48.       }
  49.     }
  50.     if (((*edge++) & M_END_OF_NODE) != 0) break;
  51.   }
  52.   return(0!=0);
  53. }
  54.  
  55. int
  56. #ifdef PROTOTYPES
  57. dawg_check(NODE PCCRAP *dict, char *word)
  58. #else
  59. dawg_check(dict, word)
  60. NODE PCCRAP *dict;
  61. char *word;
  62. #endif
  63. {
  64.   return(dawg_ck(dict, dict+ROOT_NODE, word));
  65. }
  66.  
  67. static int
  68. #ifdef PROTOTYPES
  69. pack_ck(NODE PCCRAP *ptrie, INDEX p, char *s)
  70. #else
  71. pack_ck(ptrie, p, s)
  72. NODE PCCRAP *ptrie;
  73. INDEX p;
  74. char *s;
  75. #endif
  76. {
  77. /* Note: node is passed in as a parameter so that it is in a register -
  78.    otherwise it would take an extra instruction every time it was accessed.
  79.    We trust the compiler to allocate register variables most efficiently --
  80.    when people tinker, it might improve one machine but ruin another...
  81.  */
  82.  
  83. #define next_letter(s) \
  84.   p = ptrie[p + *s]; \
  85.   if (((p >> V_LETTER) & M_LETTER) != *s++) return(0!=0); \
  86.   if (*s == '\0') return((p >> V_END_OF_NODE) != 0); \
  87.   if ((p &= M_NODE_POINTER) == 0) return(0!=0)
  88.  
  89.   /* Depending on whether your machine has a cache or not, and whether
  90.      it optimises pipeline fetches, you should decrease or increase the
  91.      number of macro instantiations in the loop below appropriately */
  92.  
  93.   for (;;) {
  94.     next_letter(s);    next_letter(s);    next_letter(s);    next_letter(s);
  95.   }
  96. }
  97.  
  98. int
  99. #ifdef PROTOTYPES
  100. pack_check(NODE PCCRAP *ptrie, char *s)
  101. #else
  102. pack_check(ptrie, s)
  103. NODE PCCRAP *ptrie;
  104. char *s;
  105. #endif
  106. {
  107.   return(pack_ck(ptrie, 1L, s));
  108. }
  109.